package com.gitee.feizns.explore.data_structure.array.middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author feizns
 * @since 2023/09/05
 */
public class ThreeSum {

    public static void main(String[] args) {
        threeSum(new int[]{-1, 0, 1, 2, -1, -4}).forEach(System.out::println);
    }

    /**
     * @param nums {@link int[]}
     * @return {@link List}<{@link List}<{@link Integer}>>
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if ( nums != null && nums.length >= 3 ) {
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                if ( i > 0 && nums[i] == nums[i - 1] )
                    continue;
                //期望值
                int desiredValue = nums[i];
                twoSums(nums, i + 1, nums.length - 1, -desiredValue)
                        .stream()
                        .peek(list -> list.add(0, desiredValue))
                        .forEach(results::add);
            }
        }
        return results;
    }

    /**
     * @return {@link List}<{@link List}<{@link Integer}>>
     */
    public static List<List<Integer>> twoSums(int[] nums, int left, int right, int desiredValue) {
        List<List<Integer>> result = new ArrayList<>();
        while ( left < right ) {
            int value = nums[left] + nums[right];
            if ( value == desiredValue )
                result.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
            //
            if ( value > desiredValue ) {
                do {
                    right--;
                } while ( right > left && nums[right] == nums[right + 1] );
            } else {
                do {
                    left++;
                } while ( left < right && nums[left] == nums[left - 1] );
            }
        }
        return result;
    }

}
